\chapter{条件变量}
\thispagestyle{empty}

%\section{引言}
目前，我们已经开发出了锁，并且已经知道如果正确地结合硬件和操作系统的支持来构造锁。不幸的是，要编写并发程序不仅仅需要锁这一个原语。

特别的，许多情况下，一个线程希望在继续执行之前检测某个条件是否为真。例如，父线程在继续执行前想检测子线程是否完成（通常调用join()）；该如何实现这样的等待呢？先来看看图30.1

图30.1

我们想要看到的结果应该是这样的：

parent: begin\\
child\\
parent: end\\

我们可是尝试一下共享变量，见图30.2。这个方法通常是可行的，但是父线程作无谓的自旋浪费CPU时间，这也太低效了吧。我们想要的是一种可以让父线程在某个条件（比如子线程执行结束）为真之前一直休眠的方法。

图30.2

Crux:如何等待某个条件
在多线程程序中，在继续执行之前等待某个条件为真通常是很有用的。简单的方法就是自旋至该条件为真，但这是极其浪费CPU时间的，并且有些时候还不一定正确。那么，线程该如何等待条件呢？


\section{定义和例程}
为了等待某个条件变为真，线程可以使用众所周知的条件变量。条件变量是一个队列，多个线程可以在某些执行状态（比如条件）还未满足时将自己加入该队列中（以等待该条件）；当其他线程改变前面的那个状态时，就可以唤醒其中一个（或多个）等待线程，从而是的等待线程可以继续执行（通过该条件的signaling）。这个思想要追溯到Dijkstra使用的”私有信号量“[D68]；后来Hoare在他monitors的工作中提出了类似的思想”条件变量“。

要声明一个条件变量，简单的写这样即可：pthread\_cond\_t c;，这行代码将c声明为一个条件变量（注意：需要正确的初始化）。条件变量有两个与之关联的操作：wait()和signal()。wait()调用在线程希望将其自己休眠时执行；signal()调用则在某个线程改变了某个状态且想要唤醒某个休眠的等待线程时执行。具体的，POSIX调用如下：\\
pthread\_cond\_wait(pthread\_cond\_t *c, pthread\_mutex\_t *m);\\
pthread\_cond\_signal(pthread\_cond\_t *c);\\

后面为了简单起见，提到这两个调用时就写作wait()和signal()。你可能注意到wait()有一个mutex作为参数；一般认为这个mutex在调用wait()之前是锁住的。wait()的作用是释放这个锁并使线程进入休眠（原子地）。当线程被唤醒时（在其他线程发信号给它后），在返回调用线程前重新获得该锁。这么复杂是为了避免在线程进入休眠的时候引起竞争条件。我们看一下join问题的解决方案（图30.3），以便更好的理解。

图30.3

有两个情况要考虑一下。第一种情况是，父线程创建了子线程，但是它会继续执行（假设只有一个处理器），因此会立即调用thr\_join()等待子线程结束。这个时候，父线程会获得锁，并检查子线程是否结束（实际上没有），然后通过调用wait()是自己休眠（因此释放了锁）。轮到子线程运行时，打印消息”child“，并调用thr\_exit()唤醒父线程；thr\_exit()函数仅仅获取锁置状态变量done，并唤醒父线程。最后，父线程继续运行（在wait()中获得锁并返回），解锁并打印消息”parent: end“。

第二种情况是，子线程在被创建之后就立即得到执行，将done置为1，调用signal()唤醒休眠的线程（而实际上没有，所以直接返回），并结束。然后父线程执行，调用thr\_join()，发现done已被置为1，因此不需要等待直接返回。

最后提醒：你应该看到父线程在决定是否等待条件时，使用了while循环而不是if条件判断。虽然这看起来对于程序的逻辑没有太大的必要，但这么做总是个好习惯，下面你会看到为什么。

为确保能够理解thr\_exit()和the\_join()的重要性，我们来看一个稍作修改的版本。首先，你也许会怀疑状态变量done是否有必要存在。如果代码如下面所示呢？能够正确执行么？

代码

很遗憾，这个方法行不通。设想这么一种情况，子线程在被创建之后立即运行，调用thr\_exit()；此时，子线程会调用signal()，但没有线程在等待这个条件。当父线程运行时，只是简单地调用wait()并阻塞，然而却不会有任何线程唤醒它。从这个例子，你应该意识到状态变量done的重要性了；它记录了两个线程都想知道的状态。休眠、唤醒以及锁都是围绕着这个变量来的。

下面是另一个问题示例。这个例子，设想signal()和wait()不需要锁。会发生什么问题呢？思考一下！

代码

这里的问题是竞争条件。具体地，如果父线程调用了thr\_join()并检查done的值，它会发现done的值为0，从而调用wait()休眠。但是呢，恰恰在它调用wait()之前，被中断了，然后子线程运行。子线程改变了置状态变量done为1并调用signal()，而实际上没有线程等待，因此也就没有线程被唤醒。当父线程在此运行时，它就只能一直休眠了。

TIP：signal时一定要加锁。
尽管不是所有的情况都需要严格这么做，但是，使用条件变量signal时加锁是最简单也是最好的方法。上面的例子表明要保证正确性就必须加锁；然而，有些情况不加锁也可以，但是很可能是需要避免的情况。因此，简单起见，调用signal()时加锁。
反之，在调用wait()时加锁就不是一个建议了，而是由wait()的语义决定的，因为wait()总是（a）认为在调用它时锁是被持有的，（b）调用者进入休眠时释放该锁，（c）在返回时再次获取该锁。因此，本tip的概括是正确的：调用signal()和wait()时加锁，这样你总是不错的。

希望在这个简单的join例子中，你们能够明白一些正确使用条件变量的基本要求。为确保你们能够理解，下面在看一个稍复杂的例子：生产者/消费者或有限缓冲区问题。



\section{生产者/消费者（有限缓冲区）问题}
本章要面临的同步问题是：生产者/消费者问题，有时候也称作有限缓冲区问题，是Dijkstra首先提出[D72]。是的，就是这个生产者/消费者问题让Dijkstra和他的合作者发明了广泛使用的信号量（可被用作锁或者条件变量）[D01]；稍后我们会详细学习信号量。

设想一个或多个生产者线程和一个或多个消费者线程。生产者产生数据并将之放入缓冲区；消费者从缓冲区中取出那些数据，然后以某种方式处理这些数据。

这样的模式存在于许多实际系统中。例如，多线程web服务器中，生产者将HTTP请求放入工作队列中（比如有限缓冲区）；消费者线程从队列中取出请求并处理。

当你将某个程序的输出作为另一个程序的输入时（比如管道）也会用到有限缓冲区，例如，grep foo file.txt | wc -l。这个例子并发的运行了两个进程；grep将file.txt中包含foo串的行写入标准输出；UNIX shell将该标准输出重定向到UNIX管道pipe中（由pipe系统调用构造）。这个管道的另一端是wc进程的标准输入，wc简单的统计输入流的行数并打印出来。因此grep进程是一个生产者；wc进程就是一个消费者；两者之间是一个内核有限缓冲区；这个例子里，你只是非常方便的使用了这些工具。

由于有限缓冲区是一个共享资源，对它的访问当然需要同步，以避免发生竞争条件。为更好的理解这个问题，我们来测试几个实际代码。

首先需要一个生产者可以放入、消费者可以取出的共享缓冲区。 这里就简单的使用一个整型数来表示（当然也可以在此处用一个指针指向一个数据结构），以及一个将值放入缓冲区的函数和一个将值从缓冲区取出的函数。详见图30.4。

图30.4

相当简单，是吧！put()函数假设缓冲区是空的（通过断言来检查），然后简单地将值放入共享缓冲区并标记count为1以示缓冲区已满。get()函数正好相反，将缓冲区置为空（置count为0）并返回该值。别担心这个缓冲区只有一个成员，稍后我们会将之推广至可以同时存放多个成员的队列，这样会比看起来更有意思一些。

现在我们需要再写几个函数，用来在放入数据或者获取数据时帮助获知什么时候可以访问缓冲区。满足缓冲区的访问权限的条件很明显：只有当count为0时可以将数据放入缓冲区（此时缓冲区为空），只有count为1时可以获取缓冲区数据（此时缓冲区满）。如果我们写出来的是同步代码，会使得生产者将数据放入满缓冲区中，以及消费者从空缓冲区中去数据。这样的话肯定是错的（在这段代码里，断言will fire）。

这个测试将会由两类线程完成，一类称作生产者线程，另一类是消费者线程。见图30.5。其中生产者将一个整数放入共享缓冲区loops次，消费者不停的从缓冲区中取出数据，每次将取出的数据打印出来。

图30.5

\textbf{A Broken Solution}\\
现在假设只有一个生产者和一个消费者。明显，put()函数和get()函数之间存在临界区，put()更新缓冲区以及get()读取缓冲区。然而，在临界区周围添加锁没有用，还需要一些东西。不出意料，需要的东西就是条件变量。在第一次失败尝试中（图30.6），仅有一个条件变量cond和对应的锁mutex。

图30.6

下面我们来测试一下表30.1中生产者与消费者间的执行逻辑。当生产者想填充缓冲区时，就等待缓冲区为空（p1-p3）。消费者的执行逻辑也一样，不同的是等待条件是缓冲区不为空（c1-c3）。

表30.1

只有一个生产者和一个消费者时，图30.6中的代码是可行的。然而，如果不止一个时（比如两个消费者），该代码中就有两个临界问题。哪两个呢？

...（停下来想想看）...

我们来看第一个问题，在wait之前的if语句。假设有两个消费者（Tc1和Tc2）以及一个生产者（Tp）。首先，一个消费者运行（Tc1）；申请获取锁（c1）并是否有缓冲区已经准备就绪以供使用（c2），发现没有就等待（c3）（此时锁已释放）。

然后生产者（Tp）运行。它首先获取锁（p1），检测缓冲区是否已满（p2），发现未满就像其中填充（p4）。接着生产者通知等待线程缓冲区已经有数据（p5）。注意，这个操作将第一个消费者（Tc1）从休眠中移入就绪队列中；Tc1现在已经有条件运行了（但还未运行）。生产者继续填充直到缓冲区已满，此时生产者进入休眠状态（p6，p1-p3）。

这时就会出现这样的问题：另一个消费者（Tc2）会偷偷的进入执行并取走缓冲区中已存在的值（c1, c2, c4, c5, c6, 由于缓冲区已满就跳过了c3的等待）。此时假设Tc1运行；wait返回之前重新获取锁并返回。它接着调用get()（c4），但是此时缓冲区已经没有数据可供使用！这就出发了断言，且代码未能如预期的功能那样。明显，我们应该采取些措施阻止Tc1消费数据，因为Tc2已经偷偷的执行并消费了缓冲区的数据。表30.1显示了每个线程的动作，以及其调度状态（就绪、运行、休眠）。

这个问题是由一个简单的原因产生的：在生产者唤醒Tc1之后，但在Tc1运行之前，有界缓冲区的状态发生了变化（由于Tc2）。向线程发送信号仅仅是唤醒他们，而表明缓冲区的状态已改变（此时，已经放入了一个值到缓冲区中），但是并没有保证到被唤醒的线程执行前该状态仍然保持不变。在首次用这个方法构建了条件变量的研究之后，这段信号意思的解释即通常被称作Mesa语义（加脚注：the signaled thread transitions back to the ready state）[LR80]；相反的（被称作Hoare语义）会更难构建，但提供了更强的保证是的被唤醒的线程可以在被唤醒之后立即运行[H74]。实际上所有系统都曾使用过Mesa语义。

\textbf{更好但仍然broken：while，not if}\\
幸好，这个修改很容易（图30.7）：将if变成while。想想看为何这么做可行；现在消费者Tc1被唤醒并立即再检查共享变量的状态（c2）。如果缓冲区的此时是空的，那么消费这就简单地再休眠（c3）。生产者里的对应的if也改成while（p2）。

图30.7

多亏Mesa语义，使用条件变量要记住的就是一定要用while循环。有时候，你不必重新检查条件，但是这么做总不会错；就开心的这么做吧。

然而，这段代码仍然有一个bug，第二个问题前面已经提到过了。知道了么？这里只有一个条件变量，需要想办法解决这个问题。试着在看下面的代码前自己解决这个问题。尝试吧！

...（停下来想一想，或者闭上眼睛）...

现在我们对照一下是否正确解决了，或者确认一下你现在睁开了眼且在阅读这部分。这个问题发生在两个消费者（Tc1和Tc2）第一次运行也都进入了休眠（c3）。那么生产者运行时，将值放入缓冲区，唤醒其中一个消费者（假定Tc1）并进入休眠。此时，有一个消费者已就绪准备运行（Tc1），有两个线程为一个条件变量休眠（Tc2和Tp）。那么问题就放生了：事情就变得好玩儿了！

接着消费者Tc1从wait()返回从而唤醒（c3），重新检测条件（c2）并发先缓冲区是满的，然后取出该值（c4）。然后这个消费者对该条件发送信号（c5），唤醒其中一个正在休眠的线程。但是，该唤醒那个线程呢？

由于消费者已经清空了缓冲区，很明显它要唤醒生产者。然而，如果它唤醒了消费者Tc2（这明显是有可能的，这取决于等待队列是如何管理的），那就有问题了。具体来说，消费者Tc2会被唤醒并发现缓冲区是空的（c2），然后继续休眠（c3）。有值要放入缓冲区的生产者Tp就被丢一边休眠了。其他的消费者线程Tc1仍然休眠。那么全部三个线程都进入休眠了，很明显是一个bug；这个可怕灾难的具体步骤见表30.2。

信号是肯定需要的，但是必须要更加明确。消费者不能唤醒其他消费者，只能是生产者，反之亦然。

\textbf{单缓冲区生产者/消费者问题解决方案}\\
这里的方案仍然是个小方法：使用两个条件变量，而不是一个，确保在系统状态噶生变化时，向应该被唤醒的线程发送信号。代码见图30.8。

图30.8

上述的代码，生产者线程等待在empty条件以及向fill发信号。相反的，消费者线程等待在fill条件上并向empty发信号。这么做，上述的第二个问题就通过设计避免了：消费者不可能碰巧唤醒另一个消费者，生产者也不可能唤醒另一个生产者。


\textbf{生产者/消费者最终方案}\\
现在我们已经有了一个可行的生产者/消费者问题的解决方案，尽管不是完全通用。最后要修改的是使之能支持更高的并发度和更好的效率；具体地，增加更多的缓冲槽，这样生产者再休眠前就可以生产更多的值，类似的，消费者线程也可以在休眠前处理多个数据。对于仅有一个生产者和消费者来说，这个方法可以更加有效的减少上下文切换的次数；对于多生产者和消费者来说，也支持并发的生产或消费同时发生，因此也提高了并发性。幸好，这只是对目前方案很小的一个改变。

这个最终方案的第一个改变是缓冲数据结构本身和对顶的put()和get()函数（图30.9）。我们此外，还对生产者和消费者用来判断是否休眠的条件变量做了一些变化。图30.10则是最终方案的等待和信号逻辑。生产者仅在所有的缓冲区被填满时休眠（p2）；类似的，消费者仅仅在缓冲区空时休眠（c2）。至此我们解决了生产者/消费者问题。

图30.9和30.10

TIP：为条件变量使用while而非if
在多线程程序中检测条件变量时，使用while循环总是不错的；使用if语句则是可能正确，这取决于信号的语义（译注：底层操作系统的实现）。因此，一定要使用while循环，这样你的代码才会如你预期的样子执行。
在检测条件变量时使用while循环也可以防止虚假唤醒发生。在某些线程库中，由于实现细节，所以有可能两个线程都被唤醒，即使只有一个唤醒信号发生[L11]。虚假唤醒是一个等待线程重新检测条件变量的另一个原因。


\section{covering conditions}
我们再来看一个关于如何使用条件变量的例子。这段代码摘自Lampson和Redell的Pilot论文[LR80]，跟第一个实现了上面提到的Mesa语义的是同一个团队（用的是Mesa语言，所以叫这个名字）。

在简单多线程内存分配库，他们遇到的问题最好用一个简单的例子来展示一下。图30.11的代码即说明了这个问题。

图30.11

考虑这样一个场景。假设有0字节的内存空闲；线程Ta调用allocate(100)，接着线程Tb通过调用allocate(10)请求较少的内存。Ta和Tb都因此等待条件而休眠；两个线程都没有足够多的内存以满足请求。

假设，此时第三个线程Tc调用free(50)。不幸地是，当它调用signal来唤醒线程时，他可能不会唤醒本该唤醒的只申请10字节的线程Tb；由于没有仍没有足够的内存，Ta应该继续休眠。因此图中的代码对于此问题不可行，由于线程唤醒其他线程时步子换到那个线程该被唤醒。

Lampson和Redell建议的解决方案很直接：不使用pthread\_cond\_signal()调用，而是使用pthread\_cond\_broadcast()，唤醒所有等待线程。这么做，我们就可以保证任意该被唤醒的线程都会被唤醒。当然，缺点就是会性能有负面影响，因为有很多等待线程不需要被唤醒。那些线程仅仅简单的唤醒，再检测条件，然后继续休眠。

Lampson和Redell称这样的条件为covering condition，因为它覆盖了所有的需要被唤醒的线程；代价就是有太多的线程会被唤醒（正如我们上面讨论的）。聪明的读者可能已经注意到我们更早的时候就已经用了这个方法了（见仅使用一个条件变量的生产者/消费者问题）。然而，在那种情况下，有更好的解决方法，因此我们就不采用这个方法。通常，如果你发现只有将代码改成broadcast时才可行（不要认为这是需要的），你多半是有bug了；那就修复它吧！在上述的内存分配情况下，采用broadcast是可用的最直接的方法。


\section{小结}
我们已经明白了除lock之外的另一个重要的同步原语：条件变量。通过让线程在某些程序状态未满足时进入休眠，条件变量使得我们可以优雅的解决许多重要的同步问题，包括著名的也仍然很重要的生产者/消费者问题，以及covering conditions。A more dramatic concluding sentence would go here, 比如”He loved Big Brother”[O49]。


